#include<iostream>
#include<string>
using namespace std;

class Smallsum{
public:
	int merge(int arr[],int L,int R,int M){
		int res = 0;
		int * cp_arr  = new int[R-L+1];
		int pl1 = L;
		int pl2 = M+1;
		int i = 0;
		while(pl1 <= M && pl2 <= R){
			if(arr[pl1]>=arr[pl2]){
				cp_arr[i] = arr[pl2];
				i++;
				pl2++;
			}
			else{
				cp_arr[i] = arr[pl1];
				res += arr[pl1] * (R - pl2 +1);
				i++;
				pl1++;
			}

		}
		while(pl1<=M){
			cp_arr[i] = arr[pl1];
			i++;
			pl1++;
		}
		while(pl2<=R){
			cp_arr[i] = arr[pl2];
			i++;
			pl2++;
		}
		for(int j=0;j<(R-L+1);j++){
			arr[L+j] = cp_arr[j];
		}
		if(cp_arr != NULL){
			delete[] cp_arr;
			cp_arr = NULL;
		}
		return res;
	}
	int process(int arr[],int L,int R){
		if(L==R){
			return 0;
		}
		int mid =L+((R-L)>>1);
		return process(arr,L,mid)+process(arr,mid+1,R)+merge(arr,L,R,mid);

	}
};
void test01(){
	Smallsum s1;
	int arr[5]{4,1,2,6,7};
	cout<<"smallsum = "<<s1.process(arr,0,4)<<endl;
}
int main(){
	test01();

	return 0;
}
